//
//  162. 寻找峰值.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/8/29.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution162 {
    // 解法一: 只需要大于左边并小于右边即可
    // 这个是on的解法
    func findPeakElement(_ nums: [Int]) -> Int {
        var pre = Int.min
        var result = 0
        for i in 0..<nums.count {
            let item = nums[i]
            let next = i + 1 < nums.count ? nums[i + 1]: Int.min
            if item > pre, item > next {
                result = i
                break
            }
            pre = item
        }
        return result
    }
    // 向这种简单的题应该有更快点额解法,二分法
    // 用二分法能快速的区分高点值在哪里,所以实际复杂度要更快一点
    // 最终只有一个元素时，即为峰值
    // logn的时间复杂度
    func findPeakElement2(_ nums: [Int]) -> Int {
        var left = 0
        var right = nums.count - 1
        while left < right {
            let mid = (left + right) / 2
            if nums[mid] > nums[mid + 1] {
                // 峰值元素在其左边
                right = mid
            } else {
                // 峰值元素在其右边
                left = mid + 1
            }
        }
        return right
    }
    static func test() {
        let solution = Solution162()
//        let nums =  [1,2,3,1]
        let nums =  [1]
        let result = solution.findPeakElement(nums)
        print(result)
    }
}
